package danran.bfs;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Classname UpdateMatrix
 * @Description TODO
 * @Date 2021/9/21 20:09
 * @Created by ASUS
 */
public class UpdateMatrix {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int[][] updateMatrix(int[][] mat) {
        int[][] ans = new int[mat.length][mat[0].length];
        for (int i = 0; i < ans.length; i++) for (int j = 0; j < ans[0].length; j++) ans[i][j] = -1;
        boolean[][] visited;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    int step = 0;
                    visited = new boolean[mat.length][mat[0].length];
                    loop:
                    while (!q.isEmpty()) {
                        int size = q.size();
                        step++;
                        for (int k = 0; k < size; k++) {
                            int[] cur = q.poll();
                            assert cur != null;
                            for (int[] dir : dirs) {
                                int x = cur[0] + dir[0], y = cur[1] + dir[1];
                                if (x < 0 || x == mat.length || y < 0 || y == mat[0].length) continue;
                                if (mat[x][y] == 0) {
                                    ans[i][j] = step;
                                    q.clear();
                                    break loop;
                                } else {
                                    if (ans[x][y] != -1) {
                                        ans[i][j] = step + ans[x][y];
                                    }
                                    if (!visited[x][y]) {
                                        q.offer(new int[]{x, y});
                                        visited[x][y] = true;
                                    }
                                }
                            }
                        }
                    }
                } else ans[i][j] = 0;
            }
        }
        return ans;
    }

    private int row;
    private int col;
    private int[][] vector = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * DP（两次遍历，可 AC）
     */
    public int[][] updateMatrix_1(int[][] matrix) {
        row = matrix.length;
        col = matrix[0].length;
        // 第一次遍历，正向遍历，根据相邻左元素和上元素得出当前元素的对应结果
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = row + col;
                }
                if (i > 0) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i - 1][j] + 1);
                }
                if (j > 0) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][j - 1] + 1);
                }
            }
        }
        // 第二次遍历，反向遍历，根据相邻右元素和下元素及当前元素的结果得出最终结果
        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                if (i < row - 1) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i + 1][j] + 1);
                }
                if (j < col - 1) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][j + 1] + 1);
                }
            }
        }
        return matrix;
    }

}
